package com.itheima.algorithm.binarytree;

import com.itheima.algorithm.stack.LinkedListStack;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author: TylerZhong
 * @description:
 */
public class E03Leetcode145 {

    static class TreeNode {
        TreeNode left;
        int val;
        TreeNode right;

        public TreeNode(TreeNode left, int val, TreeNode right) {
            this.left = left;
            this.val = val;
            this.right = right;
        }
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> lists = new ArrayList<>();

        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode curr = root; // 代表当前节点
        TreeNode pop = null; // 最近一次弹栈的元素
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr); // 压入栈，为了记住回来的路
                // 待处理左子树
                curr = curr.left;
            } else {
                TreeNode peek = stack.peek();
                if (peek.right == null) { // 没有右子树
                    pop = stack.pop();
                    lists.add(pop.val);
                } else if (peek.right == pop) { // 右子树处理完成
                    pop = stack.pop();
                    lists.add(pop.val);
                } else { // 待处理右子树
                    curr = peek.right;
                }
            }
        }
        return lists;
    }

    public void test2() {
        TreeNode root = new TreeNode(
                new TreeNode(
                        new TreeNode(null, 4, null),
                        2,
                        new TreeNode(null, 7, null)
                ),
                1,
                new TreeNode(
                        new TreeNode(null, 5, null),
                        3,
                        new TreeNode(null, 6, null)
                )
        );

        LinkedListStack<TreeNode> stack = new LinkedListStack<>(10);
        TreeNode curr = root; // 代表当前节点
        TreeNode pop = null; // 最近一次弹栈的元素
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr); // 压入栈，为了记住回来的路
                // 待处理左子树
                colorPrintln("前--："+curr.val, 31);
                curr = curr.left;
            } else {
                TreeNode peek = stack.peek();
                if (peek.right == null) { // 没有右子树
                    System.out.println("中=========================="+peek.val);
                    pop = stack.pop();
                    colorPrintln("后=========：" + pop.val, 34);
                } else if (peek.right == pop) { // 右子树处理完成
                    pop = stack.pop();
                    colorPrintln("后=========：" + pop.val, 34);
                } else { // 待处理右子树
                    System.out.println("中=========================="+peek.val);
                    curr = peek.right;
                }
            }
        }
    }

    // 后续遍历
    public void postOrder(TreeNode root) {
        /*TreeNode root = new TreeNode(
                new TreeNode(
                        new TreeNode(null, 4, null),
                        2,
                        new TreeNode(null, 7, null)
                ),
                1,
                new TreeNode(
                        new TreeNode(null, 5, null),
                        3,
                        new TreeNode(null, 6, null)
                )
        );*/

        LinkedListStack<TreeNode> stack = new LinkedListStack<>(10);
        TreeNode curr = root; // 代表当前节点
        TreeNode pop = null; // 最近一次弹栈的元素
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                colorPrintln("去："+curr.val, 31);
                stack.push(curr); // 压入栈，为了记住回来的路
                curr = curr.left;
            } else {
                TreeNode peek = stack.peek();
                if (peek.right == null || peek.right == pop) {
                    pop = stack.pop();
                    curr = pop.right;
                    colorPrintln("回：" + pop.val, 34);
                } else {
                    curr = peek.right;
                }

            }
        }
    }

    private static void colorPrintln(String origin, int color) {
        System.out.printf("\033[%dm%s\033[0m%n", color, origin);
    }

}
